Section: New Results

Soft Problems (modelling and filtering)

Participants : Thierry Petit, Alexis De Clerq, Nicolas Beldiceanu, Narendra Jussien.

1. Side-constrained problems We experimentally shown that solving some classes of over-constrained problems requires an efficient (global) propagation of side constraints on variables representing violations. This work completes our previous studies, which highlighted the interest of a variable-based representation of violations for sake of modelling.

   The corresponding paper Global Propagation of Side Constraints for Solving Over-constrained Problems was published in the Annals of Operations Research journal [14] .

2. Soft cumulative scheduling We proposed a new constraint for handling cumulative problems with exceeds of capacities, int the case where the time horizon is fixed and the capacity can vary over time. Sweep and Edge-finding algorithms for classical cumulative problems have been modified so as to provide a filtering algorithm for our constraint. Experiments shown that instances involving several hundreds of activities can be solved with our approach.

   The corresponding paper Filtering Algorithms for Discrete Cumulative Problems with Over-loads of Resource was published at the 17th International Conference on Principles and Practice of Constraint Programming (CP 2011 ), [17] .